package com.ryujung.binary_tree.leetCode_102;

import java.util.*;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    /**
     * 思路：
     * 由根节点依次向下遍历，将当前层级的所有节点保存在队列中FIFO
     * <p>
     * 然后再逐个取出节点，放入当前层级的list中，并用另一个队列保存节点的左右子树节点，
     * 当目前层级的队列被清空时，就指向下一层级，并提交当前层级的list到result中
     * <p>
     * 然后进入下个整个循环
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return Collections.EMPTY_LIST;

        List<List<Integer>> res = new ArrayList<>();

        Deque<TreeNode> que = new LinkedList<>();
        Deque<TreeNode> nque = new LinkedList<>();
        List<Integer> curList = new ArrayList<>();
        que.push(root);

        while (!que.isEmpty()) {
            TreeNode curNode = que.pollLast();
            curList.add(curNode.val);

            if (curNode.left != null) {
                nque.push(curNode.left);
            }
            if (curNode.right != null) {
                nque.push(curNode.right);
            }
            if (que.isEmpty()) {
                que = nque;
                nque = new LinkedList<>();
                res.add(new ArrayList<>(curList));
                curList = new ArrayList<>();
            }

        }

        return res;
    }
    // 时间复杂度：O(n)，需要完整遍历树
    // 空间复杂度：O(n)，使用两个队列来保存当前遍历的层，以及当前层的子树节点。

    /**
     * 尝试使用标准的BFS 广度优先算法，只使用一个队列来完成层序遍历
     */
    public static List<List<Integer>> levelOrder2(TreeNode root) {
        if (root == null) return Collections.EMPTY_LIST;

        List<List<Integer>> res = new ArrayList<>();

        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            List<Integer> curList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                curList.add(node.val);

                if (node.left != null)
                    que.add(node.left);

                if (node.right != null)
                    que.add(node.right);
            }
            res.add(curList);
        }

        return res;
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node4.right = node5;

        System.out.println(levelOrder(node));
    }
}